package codingforgreat.class27;

import java.util.Arrays;

public class Class02_MinPeople {
    //	题目二：
//	企鹅厂每年都会发文化衫，文化衫有很多种，厂庆的时候，企鹅们都需要穿文化衫来拍照
//  一次采访中，记者随机遇到的企鹅，企鹅会告诉记者还有多少企鹅跟他穿一种文化衫
//  我们将这些回答放在 answers 数组里，返回鹅厂中企鹅的最少数量。
//	输入: answers = [1]    输出：2
//	输入: answers = [1, 1, 2]    输出：5
//  Leetcode题目：https://leetcode.com/problems/rabbits-in-forest/
//
//思路：x个相同的 有 x/x+1 向上取整  当有C个人 说 有x人和自己相同时 有 (c/(x+1)) 向上取整 ((c + x) / (x + 1)) * (x + 1) 个人
    public static int minPeople(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        Arrays.sort(arr);
        int x = arr[0];
        int c = 1;
        int res = 0;
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] == arr[i - 1]){
                c++;
            }else{
                res += ((c + x) / (x + 1)) * (x + 1);
                x = arr[i];
                c = 1;
            }
        }
         return res + ((c + x) / (x + 1)) * (x + 1);
    }
}
